home *** CD-ROM | disk | FTP | other *** search
/ TPUG - Toronto PET Users Group / TPUG Users Group CD / TPUG Users Group CD.iso / AMIGA / AMICUS / AMICUS02.ADF / Asm / qsort.asm < prev    next >
Assembly Source File  |  1989-05-30  |  9KB  |  297 lines
  1.          RORG  0
  2.          XDEF _qsort
  3. * The qsort algorithm implemented in 68000 assembler.
  4. * This routine implements the quick sort for any arbitrary data array of
  5. * any arbitrary size.  The sort is "in-place" in the array, no temporary
  6. * space is needed aside from a little stack space.  I have tried to keep
  7. * this as close to the Unix conventions of qsort as possible.  I don't
  8. * think there are any bugs, but who knows.
  9. *              Gary Sarff  12/07/85   Compuserve PPN 70167,2216
  10. *
  11. * Calling convention/declaration from Lattice C programs is:
  12. *
  13. * void qsort((char *)base,nel,sizeof (*base),compar)
  14. * unsigned int nel;
  15. * int (*compar)();
  16. *
  17. * base points to the base element of the table to be sorted.
  18. * nel is the number of elements in the table.
  19. * compar is the name of the comparison function, which is called with two
  20. * arguments that point to the elements being compared.  The function
  21. * must return an integer less than, equal to, or greater than zero
  22. * according as the first argument is to be considered less than, equal to,
  23. * or greater than the second.
  24. * for example:
  25. * suppose array is declared as:
  26. *    struct junk { int xpart;
  27. *                  int ypart;
  28. *                  char *message[20];
  29. *                } *array[10];
  30. * Then array points to the first of ten identical structures like junk.
  31. * say if we want to sort the array on the xpart then call qsort like:
  32. *  qsort((char *)array,10,sizeof(*array),compar);
  33. *  you should find sizeof(*array) to be 24 since array is a pointer to
  34. *  something of type junk and each thing is 24 bytes long.
  35. *
  36. * Notes:  The pointer to the base table should be of type
  37. * pointer-to-element, and cast to type pointer-to-character.  The comparison
  38. * function need not compare every byte, so arbitrary data may be contained in
  39. * the elements in addition to the values being compared.  In this case only
  40. * compare the xparts of the two values passed (see below).
  41. * Although declared as pointer-to-character, the value returned should be
  42. * cast into type pointer-to-element.
  43. *
  44. * the compar function should be declared as (of course use any name you
  45. * want as long as you pass the name to qsort.)
  46. *
  47. * int compar(first,second)
  48. * and declare first and second as type pointer-to-element.  They must be
  49. * declared this way, not as pointer to char or something else, so then you
  50. * can say:
  51. *    if (first->xpart < second->xpart) return (-1);
  52. *    if (first->xpart == second->xpart) return 0;
  53. *    if (first->xpart > second->xpart) return 1;
  54. *
  55. *--------------------------------------------------------------------------
  56. *
  57. _qsort:
  58.          link     a6,#-4
  59.          move.l   20(a6),cmpaddr
  60.          move.l   16(a6),nel
  61.          move.l   16(a6),(sp)
  62.          move.l   12(a6),-(sp)
  63.          bsr.l    unsgmul          * multiply nel by sizeof elements
  64.          addq.l   #4,sp
  65.          add.l    8(a6),d0
  66.          move.l   d0,(sp)
  67.          move.l   8(a6),-(sp)
  68.          bsr.s    qcont
  69.          unlk     a6
  70.          rts
  71. qcont:
  72.          link     a6,#-4
  73.          movem.l  d0/d5-d7/a2/a4-a5,-(sp)
  74.          move.l   nel,d7
  75. QL0:
  76.          move.l   12(a6),d0
  77.          sub.l    8(a6),d0
  78.          move.l   d0,d5
  79.          cmp.l    d7,d0
  80.          bls.l    done1
  81.          move.l   d7,d0
  82.          add.l    d0,d0
  83.          move.l   d0,(sp)
  84.          move.l   d5,-(sp)
  85.          bsr.l    unsgdiv
  86.          addq.l   #4,sp
  87.          move.l   d0,(sp)
  88.          move.l   d7,-(sp)
  89.          bsr.l    unsgmul
  90.          addq.l   #4,sp
  91.          move.l   d0,d5
  92.          move.l   8(a6),d0
  93.          add.l    d5,d0
  94.          movea.l  d0,a2
  95.          move.l   a2,-4(a6)
  96.          movea.l  8(a6),a5
  97.          move.l   12(a6),d0
  98.          sub.l    d7,d0
  99.          movea.l  d0,a4
  100.          bra.s    compout
  101. comploop:
  102.          suba.l   d7,a2
  103.          move.l   a2,(sp)
  104.          move.l   a5,-(sp)
  105.          bsr.l    auxfunc
  106.          addq.l   #4,sp
  107.          bra.s    compout
  108. complt:
  109.          move.l   a2,(sp)
  110.          move.l   a5,-(sp)
  111.          movea.l  cmpaddr,a0
  112.          jsr      (a0)        * call the user provided compar function
  113.          addq.l   #4,sp
  114.          move.l   d0,d6
  115.          beq.s    comploop
  116.          tst.l    d6
  117.          bge.s    compge
  118. QL1:     adda.l   d7,a5
  119. compout:
  120.          cmpa.l   a2,a5
  121.          bcs.s    complt
  122.          bra.s    compge
  123.          move.l   a4,(sp)
  124.          add.l    d7,-4(a6)
  125.          move.l   -4(a6),-(sp)
  126.          bsr.l    auxfunc
  127.          addq.l   #4,sp
  128.          bra.s    compge
  129. qloop1:
  130.          move.l   a4,(sp)
  131.          add.l    d7,-4(a6)
  132.          move.l   -4(a6),-(sp)
  133.          move.l   a5,-(sp)
  134.          bsr.l    qdone
  135.          addq.l   #8,sp
  136.          adda.l   d7,a2
  137.          movea.l  a2,a5
  138.          bra.s    compge
  139. QL2:
  140.          move.l   a4,(sp)
  141.          move.l   -4(a6),-(sp)
  142.          movea.l  cmpaddr,a0
  143.          jsr      (a0)
  144.          addq.l   #4,sp
  145.          move.l   d0,d6
  146.          beq.s    compout
  147.          tst.l    d6
  148.          ble.s    seege
  149.          cmpa.l   a2,a5
  150.          beq.s    qloop1           * see if we have reached end of table
  151.          move.l   a4,(sp)
  152.          move.l   a5,-(sp)
  153.          bsr.l    auxfunc
  154.          addq.l   #4,sp
  155.          suba.l   d7,a4
  156.          bra.s    QL1
  157. seege:   suba.l   d7,a4
  158. compge:
  159.          cmpa.l   -4(a6),a4
  160.          bhi.s    QL2
  161.          cmpa.l   a2,a5
  162.          bne      QL3
  163.          move.l   a2,d0
  164.          sub.l    8(a6),d0
  165.          move.l   12(a6),d1
  166.          sub.l    -4(a6),d1
  167.          cmp.l    d1,d0
  168.          blt.s    QL4
  169.          move.l   12(a6),(sp)
  170.          move.l   -4(a6),d0
  171.          add.l    d7,d0
  172.          move.l   d0,-(sp)
  173.          bsr.l    qcont         * recursive call with partition of table
  174.          addq.l   #4,sp
  175.          move.l   a2,12(a6)
  176.          bra.l    QL0
  177. QL4:
  178.          move.l   a2,(sp)
  179.          move.l   8(a6),-(sp)
  180.          bsr.l    qcont         * recursive call with rest of table.
  181.          addq.l   #4,sp
  182.          move.l   -4(a6),d0
  183.          add.l    d7,d0
  184.          move.l   d0,8(a6)
  185.          bra.l    QL0
  186. QL3:
  187.          move.l   a5,(sp)
  188.          suba.l   d7,a2
  189.          move.l   a2,-(sp)
  190.          move.l   a4,-(sp)
  191.          bsr.s    qdone
  192.          addq.l   #8,sp
  193.          sub.l    d7,-4(a6)
  194.          movea.l  -4(a6),a4
  195.          bra.l    compout
  196. done1:
  197.          addq.l   #4,sp
  198.          movem.l  (sp)+,a5-a4/a2/d7-d5
  199.          unlk     a6
  200.          rts
  201. auxfunc:
  202.          link     a6,#0
  203.          movem.l  d6-d7/a4-a5,-(sp)
  204.          move.l   nel,d6
  205.          movea.l  8(a6),a5
  206.          movea.l  12(a6),a4
  207. moveloop:
  208.          move.b   (a5),d7
  209.          move.b   (a4),(a5)+
  210.          move.b   d7,(a4)+
  211.          subq.l   #1,d6
  212.          bne.s    moveloop
  213.          movem.l  (sp)+,a5-a4/d7-d6
  214.          unlk     a6
  215.          rts
  216. qdone:
  217.          link     a6,#0
  218.          movem.l  d6-d7/a3-a5,-(sp)
  219.          move.l   nel,d6
  220.          movea.l  8(a6),a5
  221.          movea.l  12(a6),a4
  222.          movea.l  16(a6),a3
  223. pivloop:
  224.          move.b   (a5),d0
  225.          ext.w    d0
  226.          ext.l    d0
  227.          move.l   d0,d7
  228.          move.b   (a3),(a5)+
  229.          move.b   (a4),(a3)+
  230.          move.b   d7,(a4)+
  231.          subq.l   #1,d6
  232.          bne.s    pivloop
  233.          movem.l  (sp)+,a5-a3/d7-d6
  234.          unlk     a6
  235.          rts
  236.          CNOP     0,4
  237. cmpaddr: DC.L     0
  238. nel:     DC.L     0
  239. *
  240. * support routines to do unsigned multiplication and division
  241. *
  242. unsgmul:
  243.          lea      4(sp),a0
  244.          move.w   (a0)+,d0
  245.          move.l   8(sp),d1
  246.          mulu     d1,d0
  247.          swap     d1
  248.          mulu     (a0),d1
  249.          add.w    d1,d0
  250.          swap     d0
  251.          clr.w    d0
  252.          move.w   (a0),d1
  253.          mulu     10(sp),d1
  254.          add.l    d1,d0
  255.          move.l   d0,-2(a0)
  256.          rts
  257. unsgdiv:
  258.          lea      4(sp),a0
  259.          movem.l  d2-d3,-(sp)
  260.          move.l   (a0),d0
  261.          move.l   d0,d2
  262.          move.l   16(sp),d1
  263.          move.l   d1,d3
  264.          cmpi.l   #$10000,d1
  265.          bge.s    adjust
  266.          clr.w    d0
  267.          swap     d0
  268.          divu     d1,d0
  269.          move.w   d0,d3
  270.          move.w   d2,d0
  271.          divu     d1,d0
  272.          swap     d0
  273.          move.w   d3,d0
  274.          swap     d0
  275.          bra.s    fini
  276. adjust:
  277.          lsr.l    #1,d0
  278.          lsr.l    #1,d1
  279.          cmpi.l   #$10000,d1
  280.          bge.s    adjust
  281.          divu     d1,d0
  282.          andi.l   #$FFFF,d0
  283.          move.l   d3,d1
  284.          swap     d1
  285.          mulu     d0,d1
  286.          swap     d1
  287.          clr.w    d1
  288.          mulu     d0,d3
  289.          add.l    d3,d1
  290.          cmp.l    d1,d2
  291.          bge.s    fini
  292.          subq.l   #1,d0
  293. fini:
  294.          move.l   d0,(a0)
  295.          movem.l  (sp)+,d3-d2
  296.          rts
  297.